#include <stdio.h>
#include "single_linked_list.cpp"

// 带头结点链表中删除一个最小结点, 假设最小结点唯一
void DeleteMinNode(LinkedList &L) {
    LNode *minPre = L; // 最小结点前驱 
    LNode *ptr = L; // 工作节点
    // 找到最小结点
    while(ptr->next != NULL) {
        if (ptr->next->data < minPre->next->data) {
            minPre = ptr;
        }
        ptr = ptr->next;
    }
    // 删除最小结点
    LNode *q = minPre->next;
    minPre->next = minPre->next->next;
    free(q);
}

// 不带头结点
void DeleteMinNode2(LinkedList &L) {
    LNode *minPre; // 最小节点前驱
    LNode *minCur = L; // 最小结点
    LNode *ptrPre;  // 工作节点前驱
    LNode *ptr = L; // 工作结点
    // 查找最小结点
    while (ptr != NULL)
    {
        if (ptr->data < minCur->data) {
            minCur = ptr;
            minPre = ptrPre;
        }
        ptrPre = ptr;
        ptr = ptr->next;
    }
    // 若最小结点的前驱为NULL, 即最小结点未被重新赋值, 即为头结点
    if (minPre == NULL) 
        L = L->next;
    else {
        minPre->next = minPre->next->next;
        free(minCur);
    }
}

int main() {
    LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 2);
    ListAppend(L, 3);
    ListAppend(L, 3);
    ListAppend(L, 7);
    ListAppend(L, 3);
    ListAppend(L, 1);
    PrintList(L);

    DeleteMinNode(L);
    PrintList(L);

    // L 默认带头结点 则L->next为不带头结点链表
    DeleteMinNode2(L->next);
    PrintList(L);
}